#include <bits/stdc++.h>

using std::min;

const int maxn=20;
const int maxm=105;

int bp[maxm],bm[maxm],fp[maxm],fm[maxm];
int t[maxm];
int dis[1<<maxn],q[1<<maxn];
char str[maxn+5];
int f,r;

inline void apply(const int &x,const int &f){
	int sta=q[x];
	if((sta&bp[f])==bp[f]&&!(sta&bm[f])){
		sta=sta&(~fm[f]);
		sta=sta|fp[f];
		if(~dis[sta]) return;
		dis[sta]=dis[q[x]]+t[f];
		q[r++]=sta;
	}
}


int main(){
	int n,m;

	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%s",t+i,str);
		for(int j=0;j<n;j++)
			if(str[j]=='+') bp[i]|=1<<j;
			else if(str[j]=='-') bm[i]|=1<<j;
		scanf("%s",str);
		for(int j=0;j<n;j++) if(str[j]=='+') fp[i]|=1<<j; else if(str[j]=='-') fm[i]|=1<<j;
	}

	f=r=0;
	memset(dis,-1,sizeof dis);
	for(dis[q[r++]=(1<<n)-1]=0;f<r;f++){
		if(!q[f]) break;
		for(int i=0;i<m;i++) apply(f,i);
	}

	//fprintf(stderr, "f=%d,r=%d\n", f,r);
	printf("%d\n",dis[0]);
	return 0;
}
